/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-04-11
 * Time:23:51
 */

/**
 * BM13 判断一个链表是否为回文结构
 *
 * 定义快慢指针 slow 和 fast，开始时都指向链表头节点。
 * 快指针每次走两步，慢指针每次走一步，直到快指针到达链表尾部，此时慢指针指向链表中间节点（当链表长度为奇数时），或者中间节点的前一个节点（当链表长度为偶数时）。
 * 将慢指针后面的链表反转。
 * 从链表头节点和反转后的链表头节点开始，比较两个链表的节点值是否相等。如果所有节点的值都相等，则链表是回文结构，否则不是回文结构。
 * 将链表反转回来，返回结果。
 */

public class isPail {
    public static void main(String[] args) {
        // 构造链表 1->2->3->2->1
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(1);

        boolean result = isPalindrome(head);

        System.out.println(result); // 输出 true，链表是回文结构
    }
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode p1 = head;
        ListNode p2 = reverse(slow);

        while (p1 != null && p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }

    private static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }
}
